c++编程 求[A,B]内素数个数

来源：百度知道 编辑：UC知道 时间：2024/05/22 10:05:28
B-A 〈=100000
A，B〈=10e+8
目前的做法都是裸搜 我会 但是会超时
我觉得奇怪的是 在用PASCAL 编的时候这种算法不会超时
但改写成C++ 就超了
老师的解释是 语言内部工作原理不同 应用筛法
所以 请高手提供筛法标程

简单调试过的。
int main()
{
unsigned int *sieve;
unsigned int nMax, nMin;
unsigned int i, j, k=0;

cout << "Please input A (A < 99900000):";
cin >> nMin;
cout << "Please input B (B > A) and (B - A) < 10^5:";
cin >> nMax;
if (nMax - nMin > 100000 || nMax > 100000000 || nMax < nMin)
{
cout << "error input" << endl;
return -1;
}

sieve = new unsigned int[(nMax - nMin + 2)];

for (i = nMin, j = 0; i <= nMax; i++, j++) //将全部数放进筛子
sieve[j] = i;

for (i = 2; i <= sqrt((double)nMax); i++)
{
for (j = 0; j <= nMax - nMin; j ++) // 寻找第一个i的倍数
{
if (sieve[j] == 0)
continue;
if (sieve[j] % i == 0)
break;
}
for (; j <= nMax - nMin; j += i) //将素数i的倍数从筛子中取出
sieve[j] = 0;
}
k = 0;
for (j